package com.cty._06_TwoExamples._68_CommonParentInTree;

/**
 * @Auther: cty
 * @Date: 2020/7/26 17:03
 * @Description: 面试题68（一）：二叉搜索树中的两个节点的最低公共祖先
 * @version: 1.0
 */
public class CommonParentInBinarySearchTree {

    public static BinaryTreeNode commonParentInTree(BinaryTreeNode treeRoot, BinaryTreeNode A, BinaryTreeNode B){

        if(isFound(treeRoot,A) && isFound(treeRoot,B)){
            while(treeRoot != null){
                if(treeRoot.value>A.value && treeRoot.value>B.value)
                    treeRoot = treeRoot.leftChild;
                else if(treeRoot.value<A.value && treeRoot.value<B.value)
                    treeRoot = treeRoot.rightChild;
                else
                    return treeRoot;
            }
        }  // end if
        return null;
    }  // end commonParentInTree()

    public static boolean isFound(BinaryTreeNode treeRoot, BinaryTreeNode node){
        if(node == null)
            return false;

        while(treeRoot != null){
            if(treeRoot.value == node.value)
                return true;
            else if(treeRoot.value > node.value)
                treeRoot = treeRoot.leftChild;
            else
                treeRoot = treeRoot.rightChild;
        }
        return false;
    }  // end isFound()

}  // end class

class BinaryTreeNode {
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}
    public BinaryTreeNode(int value){this.value = value;}
}  // end class
